package DecChallenges;

import Utils.ArrayUtils;

import java.util.Arrays;

public class Day30_P1335 {
    public static void main(String[] args) {
//        int amount = 10, max = 100;
//        int[] arr = ArrayUtils.generateArray(amount, max);
//        System.out.println("cur arr:");
//        System.out.println(Arrays.toString(arr));
//        System.out.println("max table:");
//        int[][] maxTable = getMaxTable(arr);
//        ArrayUtils.printMat(maxTable);
        int[] jobs = {6,5,4,3,2,1};
        int d = 4;
        System.out.println(minDifficulty(jobs, d));
    }
    public static int[][] getMaxTable(int[] jobs) {
        int N = jobs.length;
        int[][] record = new int[N][N];
        for(int i = 0; i < N; i++) {
            record[i][i] = jobs[i];
            if(i + 1 < N) {
                record[i][i + 1] = Math.max(jobs[i], jobs[i + 1]);
            }
        }
        for(int row = N - 3; row >= 0; row--) {
            for(int col = row + 2; col < N; col++) {
                record[row][col] = Math.max(jobs[col], record[row][col - 1]);
            }
        }
        return record;
    }
    public static int getMinDiff(int[] jobs, int[][] maxTable, int rest, int start, int[][] memo) {
        if(rest == 1) return maxTable[start][jobs.length - 1];
        if(memo[rest][start] != 0) return memo[rest][start];
        int min = 114514;
        for(int pos = start; pos < jobs.length - rest + 1; pos++) {
            if(memo[rest - 1][pos + 1] == 0) {
                memo[rest - 1][pos + 1] = getMinDiff(jobs, maxTable, rest - 1, pos + 1, memo);
            }
            min = Math.min(min, maxTable[start][pos] + memo[rest - 1][pos + 1]);
        }
        memo[rest][start] = min;
        return memo[rest][start];
    }
    public static int minDifficulty(int[] jobDifficulty, int d) {
        if(d > jobDifficulty.length) return -1;
        int[][] maxTable = getMaxTable(jobDifficulty);
        int[][] dp = new int[d + 1][jobDifficulty.length + 1];

        return getMinDiff(jobDifficulty, maxTable, d, 0, dp);
    }

}
